package linear2;

import java.util.Iterator;

public class TwoWayLinkList<T> implements Iterable<T>{

    //头结点
    private Node head;
    //最后一个结点
    private Node last;
    //链表长度
    private int N;
    public TwoWayLinkList(){
        head=new Node(null,null,null);
        last=null;
        this.N=0;
    }
    //清空线性表
    public  void clear(){
        head.next=null;
        last.pre=null;
        N=0;
    }
   //判断链表是否为空
    public boolean isEmpty(){
        return N==0;
    }

    //链表长度
    public int length(){
        return N;
    }

    //获取第n位元素
    public Node getValue(int n){
        Node value=head;
        for (int i=0;i<n;i++){
            value=value.next;
        }
        return value;
    }
    //在末尾插入元素
    public void insertLast(T t){
        if (N>0){
            Node newNode=new Node(t,null,null);
            last.next=newNode;
            newNode.pre=last;
            last=newNode;
            N++;
        }else {
            Node newNode=new Node(t,null,null);
            head.next=newNode;
            newNode.pre=head;
            last=newNode;
            N++;
        }
    }
    //在开头插入元素
    public void insertFirst(T t){
        if (N>0){
            Node newNode=new Node(t,null,null);
            head.pre=newNode;
            newNode.next=head;
            head=newNode;
            N++;
        }else {
            Node newNode=new Node(t,null,null);
            newNode.next=head;
            head.pre=newNode;
            last=head;
            N++;
        }
    }
    //向第i处插入元素
    public void insert(int i,T item){
        Node newNode=new Node(item,null,null);
        Node pre_cur=head;
        for (int n=0;n<i;n++){
            pre_cur=pre_cur.next;
        }
        newNode.pre=pre_cur;
        newNode.pre=pre_cur.next;
        pre_cur.next.pre=newNode;
        pre_cur.next=newNode;
        N++;

    }
    //删除第i个结点并返回值
    public T remove(int i){
        Node pre_cur=head;
        for (int n=0;n<i;n++){
            pre_cur=pre_cur.next;
        }

        Node cur=pre_cur.next;
        pre_cur.next=cur.next;
        cur.next.pre=pre_cur;
        N--;
        return cur.item;
    }

//获取第i处的元素
    public T get(int i){
        Node curr=head.next;
        for (int index=0;index<i;index++){
            curr=curr.next;
        }

        return curr.item;
    }
    //找到元素t首次出现的位置
    public int indexOf(T t){

        Node n=head;
        for (int index=0;n.next!=null;index++){
            n=n.next;
            if (n.item.equals(t)){
                return index;
            }

        }
        return -1;
    }
    //获取第一个元素
    public T getFirst(){
        if (isEmpty()){
            return null;
        }
        return head.next.item;
    }
    //获取最后一个元素
    public T getLast(){
        if (isEmpty()){
            return null;
        }
        return last.item;
    }

    //为了使用增强for循环而实现的方法
    //由于本身是接口，不能直接在里面实现方法
    @Override
    public Iterator<T> iterator(){
        return new TIterator();
    }
    //使用新建方法来实现的方式解决不能直接实现的问题
    public class TIterator implements Iterator{
        private Node n=head;
        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public Object next() {
            n=n.next;
            return n.item;
        }
    }


    public Node reverse(Node curr){
//        Node n=last;
//        Node nHead=head;
//        head.next=n;
//        n.next=head;
//        Node nMid;
//        //从后往前遍历，
//        while (n.pre!=nHead){
//            //元素的pre和next交换
//            nMid=n.pre;
//            n.pre=n.next;
//            n.next=nMid;
//            //找到下一个数据继续处理
//            n=n.next;
//        }
//        n.next=null;
//        last=n;
        //结束递归


        if (curr.next==null){
            //当目前元素是尾结点
            //新的head指向这个curr
            head.next=curr;
            //返回值是链表反转后的当前结点的上一个结点
            return curr;

        }
        Node pre=reverse(curr.next);
        curr.pre=pre;
        pre.next=curr;




return null;

    }

    //结点类
    private class Node{
        //存储数据
        public T item;
        //指向上一个结点
        public Node pre;
        //指向下一个结点
        public Node next;

        public Node(T item, Node pre, Node next) {
            this.item = item;
            this.pre = pre;
            this.next = next;
        }
    }
}
